package org.example.likou150.section;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Merge {
//    输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
//    输出：[[1,6],[8,10],[15,18]]
//    解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
public static void main(String[] args) {
    int[][] intervals = new int[][]{{1,4},{0,2},{3,5}};
//    int[][] intervals = new int[][]{{1,3},{2,6},{8,10},{15,18}};
    Merge merge = new Merge();
    int[][] merge1 = merge.merge(intervals);
    for (int i = 0; i < merge1.length; i++) {
        System.out.println(merge1[i][0] + " " + merge1[i][1]);
    }
}



    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        List<int[]> lists=new ArrayList<>();
        int fastIndex=1;
        int end=intervals[0][1];
        for (int i = 0; i < intervals.length;) {
            end=Math.max(end, intervals[i][1]);
            if(fastIndex<intervals.length && end >= intervals[fastIndex][0]){
                end=Math.max(end, intervals[fastIndex][1]);
                fastIndex++;
            }else {
                if(fastIndex>intervals.length){
                    fastIndex=intervals.length;
                }
                lists.add(new int[]{intervals[i][0], end});
                i = fastIndex++;
            }

        }
        return lists.toArray(new int[lists.toArray().length][]);
    }
}
